/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     random: Node | null
 *     constructor(val?: number, next?: Node, random?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */

function copyRandomList(head: Node | null): Node | null {
    if(!head) return null;
    let go: Node = head;
    while(go){
        let copy: Node= new Node(go.val,go.next); 
        go.next = copy;
        go = go.next.next;
    }
    go = head;
    while(go){
        go.next.random = go.random ? go.random.next : null;
        go = go.next.next;
    }
    let ret: Node = head.next;
    go = head;
    while(go){
        let temp: Node = go.next.next;
        go.next.next = temp ? temp.next:null;
        go.next = temp;
        go = go.next;
    }
    return ret;
};


// 执行用时：
// 76 ms
// , 在所有 TypeScript 提交中击败了
// 89.80%
// 的用户
// 内存消耗：
// 39.6 MB
// , 在所有 TypeScript 提交中击败了
// 75.51%
// 的用户

